package com.zyk.grate_offer.class04;

/**
 * 返回一个数组中，子数组最大累加和
 *
 * @author zhangsan
 * @date 2021/4/28 16:28
 */
public class Code03_MaxSumInMatrix {

    public static int maxSum(int[][] m) {
        if (m == null || m.length == 0 || m[0].length == 0) {
            return 0;
        }
        int N = m.length;
        int M = m[0].length;
        int max = Integer.MIN_VALUE;
        int cur = 0;
        for (int i = 0; i < N; i++) {
            int[] s = new int[M];
            for (int j = i; j < N; j++) {
                cur = 0;
                for (int k = 0; k < M; k++) {
                    s[k] += m[j][k];
                    cur += s[k];
                    max = Math.max(max, cur);
                    cur = Math.max(cur, 0);
                }
            }
        }
        return max;
    }

    // 流程: i行中求个最大累加和, i ~ i+1  i~i+2   i~R-1   行,
    // 优化: 可以把 i~i+1行处理成一维数组, 然后在一维数组求最大累加和
    public static int maxSum2(int[][] m) {
        if (m == null || m.length == 0) return 0;  // 非空判断
        int max = Integer.MIN_VALUE;
        int R = m.length, C = m[0].length;
        for (int r = 0; r < R; r++) {
            int[] nums = new int[C];
            for (int i = r; i < R; i++) {

                for (int c = 0; c < C; c++) {   // 把 r~i行, 加工成一维数组, 因为是慢慢滚动下来的所以+=即可从 0 ~ R-1行都求过
                    nums[c] += m[i][c];
                }
                max = Math.max(max, maxSum(nums));      // 加工完计算结果, 做统计就好

            }
        }
        return max;
    }

    public static int maxSum(int[] nums) {
        int ans = nums[0], pre = ans;
        for (int i = 1; i < nums.length; i++)
            ans = Math.max(ans, (pre = Math.max(nums[i], pre + nums[i])));
        return ans;
    }

    // 返回四个角
    public static int[] getMaxMatrix(int[][] m) {
        int r1 = 0, c1 = 0, r2 = 0, c2 = 0;
        int max = Integer.MIN_VALUE;
        int R = m.length, C = m[0].length;

        for (int r = 0; r < R; r++) {
            int[] nums = new int[C];
            for (int i = r; i < R; i++) {

                int pre = -1;
                int begin = 0;
                for (int c = 0; c < C; c++) {   // 把 r~i行, 加工成一维数组, 因为是慢慢滚动下来的所以+=即可从 0 ~ R-1行都求过
                    nums[c] += m[i][c];
                    pre += nums[c];
                    if (pre > max) {
                        max = pre;
                        r1 = r;
                        r2 = i;
                        c1 = begin;
                        c2 = c;
                    }
                    if (pre < 0) {
                        pre = 0;
                        begin = c + 1;
                    }
                }

            }
        }
        return new int[]{r1, c1, r2, c2};
    }


    // for test
    public static void main(String[] args) {
        int maxR = 100;
        int maxC = 100;
        int maxV = 40;

        int[][] m = new int[maxR][maxC];
        for (int i = 0; i < m.length; i++) {
            m[i] = generateArray(maxC, maxV, true);
        }
        int ans1 = maxSum(m);
        int ans2 = maxSum2(m);
        System.out.println(ans1);
        System.out.println(ans2);
    }


    public static int[] generateArray(int maxLen, int maxVal, boolean fixedSize) {
        maxLen = fixedSize ? maxLen : (int) (Math.random() * maxLen) + 1;
        int[] res = new int[maxLen];
        for (int i = 0; i < maxLen; i++) {
            res[i] = (int) (Math.random() * maxVal - Math.random() * maxVal);
        }
        return res;
    }

}
